#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#define MAXLEN 100

struct List {
    int len;
    int* arr;
} typedef List;

List* crateList() {
    List* res = NULL;
    res = (List*)malloc(sizeof(*res));
    if (res != NULL) {
        res->len = 0;  // ?
        res->arr = (int*)malloc(sizeof(int) * MAXLEN);
    }
    return res;
}

void delList(List* list) {
    free(list->arr);
    free(list);
    list = NULL;
}

void printList(List* list) {
    printf("[");
    for (int i = 0; i < list->len; i++) {
        if (i == list->len - 1) {
            printf("%d", list->arr[i]);
        } else {
            printf("%d, ", list->arr[i]);
        }
    }
    printf("]\n");
}
void listPush(List* list, int n) {
    if (list->len >= MAXLEN) {
        return;
    } else {
        list->arr[list->len] = n;
        list->len++;
    }
}
void inputList(List* list) {
    int n;
    printf("input a number that how many numbers you what to push in the list:");
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int num;
        scanf("%d", &num);
        listPush(list, num);
    }
}
/**
 * T1，删除最小元素，空余的位置让最后一个元素补充上
 */
int delMin(List* list) {
    if (list->len == 0) {
        return -1;
    }
    if (list->len == 1) {
        list->len = 0;
        return list->arr[0];
    }
    int minIndex = 0;
    int minValue = list->arr[0];
    for (int i = 1; i < list->len; i++) {
        if (list->arr[i] < minValue) {
            minValue = list->arr[i];
            minIndex = i;
        }
    }
    list->arr[minIndex] = list->arr[list->len - 1];
    list->len--;
    return minValue;
}
/**
 * T2 逆置，空间O1
 */
void reverseList(List* list) {
    if (list->len == 0) {
        return;
    }
    for (int left = 0; left <= list->len / 2 - 1; left++) {
        int right = list->len - left - 1;
        int temp = 0;
        temp = list->arr[left];
        list->arr[left] = list->arr[right];
        list->arr[right] = temp;
    }
}

/**
 * T3 删除值为target的元素，空间O1，时间On
 */
void removeVal(List* list, int tar) {
    if (list->len == 0) {
        return;
    }
    int right = list->len - 1;
    // 保证right指向的不是target的元素
    while (list->arr[right] == tar) {
        right--;
    }
    int left;
    for (left = 0; left < list->len; left++) {
        if (left >= right) {
            break;
        }
        if (list->arr[left] = tar) {
            // left swap right
            list->arr[left] = list->arr[right];
            list->arr[right] = tar;
            left++;
            while (list->arr[right] == tar) {
                right--;
            }
        }
    }
    list->len = left;
}
// 在有序顺序表中查找到一个元素index
int find(List* list, int tar, bool isLeft) {
    int left = -1;
    int right = list->len;
    while (left + 1 != right) {
        int mid = (left + right) >> 1;
        if (isLeft) {
            if (list->arr[mid] < tar) {
                left = mid;
            } else {
                right = mid;
            }
        } else {
            if (list->arr[mid] <= tar) {
                left = mid;
            } else {
                right = mid;
            }
        }
    }
    return right;
}
/**
 * T4 在有序顺序表中删除[S~T]之间的所有元素
 */
void removeRangeSorted(List* list, int s, int t) {
    if (s > t) {
        printf("input range error\n");
        return;
    }
    if (list->len == 0) {
        printf("list is empty!\n");
        return;
    }
    int left = find(list, s, true);
    int right = find(list, t, false);
    printf("%d\t%d\n", left, right);
    for (int i = right; i < list->len; i++) {
        list->arr[left] = list->arr[right];
        left++;
        right++;
    }
    list->len -= (right - left);
}
/**
 * T5 相对于T4来说，去掉了顺序条件
 */
void removeRange(List* list, int s, int t) {
    int* arr = (int*)malloc(4 * MAXLEN);
    int index = 0;
    for (int i = 0; i < list->len; i++) {
        if (s <= list->arr[i] && list->arr[i] <= t) {
            continue;
        }
        arr[index] = list->arr[i];
        index++;
    }
    free(list->arr);
    list->arr = arr;
    list->len = index;
}

/**
 * T6 从有序数组中删除重复元素
 */
void removeSame(List* list) {
    // ij
}
/**
 * T7 合并两个有序列表
 */
List* merge(List* list1, List* list2) {
    List* res = crateList();
    int i = 0, j = 0, index = 0;
    while (i < list1->len && j < list2->len) {
        res->arr[index++] = list1->arr[i] < list2->arr[j] ? list1->arr[i++] : list2->arr[j++];
    }
    while (i < list1->len) {
        res->arr[index++] = list1->arr[i++];
    }
    while (j < list2->len) {
        res->arr[index++] = list2->arr[j++];
    }
    res->len = list1->len + list2->len;
    return res;
}
